#include <stdio.h>
#include <stdlib.h>


typedef struct linknode
{
    int data;
    struct linknode *next;
	struct linknode *random;
}link_node;

link_node *creat()
{
    link_node *H=(link_node *)malloc(sizeof(link_node));
    H->data=0;
    H->next=NULL;
	H->random=NULL;

    return H;
}

int insert(link_node *H,int mydata)
{
    link_node *p=(link_node *)malloc(sizeof(link_node));
    link_node *q=H;
    while(H->next!=NULL)
    {   
        H=H->next;
    }   
    p->next=NULL;
    H->next=p;
    p->data=mydata;
	p->random=NULL;
    q->data++;

    return 0;
}

int view(link_node *H) 
{
    link_node *p=H;
	int mynum=0;
    while(p->next!=NULL)
    {   
        p=p->next;

		if(p->random==NULL)
		{
			mynum=0;
		}
		else
		{
			mynum=p->random->data;
		}
        printf("[%d %d]  ",p->data,mynum);

    }
    putchar(10);

    return 0;
}                                                                                                                                                                                                                                                                               

link_node *copylink(link_node *H)
{
	link_node *h=(link_node *)malloc(sizeof(link_node));
	link_node *p=H;
	while(p->next!=NULL)
	{
		p=p->next;
		link_node *a=(link_node *)malloc(sizeof(link_node));
		a->data=p->data;
		a->next=p->next;
		p->next=a;
		p=p->next;
	}
	p=H;
	while(p->next!=NULL)
	{
		p=p->next;
		if(p->random==NULL)
		{
			p->next->random==NULL;
		}
		else
		{
			p->next->random=p->random->next;
		}
		p=p->next;
	}
	p=H;
	link_node *Q=h;
	link_node *a=NULL;
	while(p->next!=NULL)
	{
		p=p->next;
		a=p->next;
		p->next=a->next;
		a->next=Q->next;
		Q->next=a;
		Q=Q->next;
	}

	return h;
}


int main(int argc, const char *argv[])
{
	link_node *H=creat();
	insert(H,10);
	link_node *a1=H->next;

	insert(H,15);
	link_node *a2=a1->next;
	
	insert(H,9);
	link_node *a3=a2->next;

	insert(H,5);
	link_node *a4=a3->next;

	insert(H,17);
	link_node *a5=a4->next;

	insert(H,2);
	link_node *a6=a5->next;

	insert(H,24);
	link_node *a7=a6->next;

	a7->random=a1;
	a6->random=a3;
	a5->random=NULL;
	a4->random=a3;
	a3->random=a2;
	a2->random=a7;
	a1->random=NULL;

	view(H);

	link_node *h=copylink(H);
	view(H);
	view(h);
	return 0;
}

